/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2020/5/19 20:21
 * @Description: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class MergeTwoLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head1 = l1;
        ListNode head2 = l2;
        ListNode head = null;
        ListNode current = null;
        if (l1.val < l2.val) {
            head = head1;
            head1 = head1.next;
        } else {
            head = head2;
            head2 = head2.next;
        }
        current = head;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }
        if (head1 == null) {
            current.next = head2;
        } else {
            current.next = head1;
        }
        return head;
    }

    public static void main(String[] argd) {
        ListNode l1 = ListNode.makeListNode(new int[]{1, 2, 4});
        ListNode l2 = ListNode.makeListNode(new int[]{1, 3, 4});
        /*ListNode.printListNode(l1);
        System.out.println("");
        ListNode.printListNode(l2);*/
        ListNode result = mergeTwoLists(l1, l2);
        ListNode.printListNode(result);
    }
}
/*
 * 利用四個标志，head1指向l1未合并的头，head2指向l2未合并的头，head指向新链表的头，current指向新链表的尾
 * 先确定头，然后比较两个链表，新链表的尾指向链表较小的值
 * 当其中一个链表结束了，新链表的尾指向另一个链表
 * */